package com.binarytree;

import java.util.ArrayList;
import java.util.List;

public class Solution26 {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) return root;

        TreeNode le = lowestCommonAncestor(root.left, p, q);
        TreeNode ri = lowestCommonAncestor(root.right, p, q);

        if (le == null && ri == null) return null;
        else if (le == null && ri != null) return ri;
        else if (le !=null && ri == null) return le;
        else return root;
    }
}
